/*
  快速排序
    1. 先从数列中取出一个数作为基准数
    2. 分区过程, 将比这个数大的数全放到他的右边, 小于他的数全放到他的左边
    3. 再对左右区间重复第二步, 知道各区间只有一个数
*/
export function quickSort<T>(arr: Array<T>): Array<T> {
  if (arr.length < 2) {
    return arr;
  }

  let left: Array<T> = [];
  let right: Array<T> = [];
  let mid = arr.splice(Math.floor(arr.length / 2), 1)[0];

  for (let i = 0; i < arr.length; i++) {
    if (arr[i] < mid) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }

  return quickSort(left).concat(mid, quickSort(right));
}

/* let chineseArr = [3, 1, 8.3555, 9, 20, 15, 2, 7, 13, 11, 19, 18, 5, 6, 17, 4];
let res = quickSort(chineseArr);
res.forEach((item) => {
  item = +item.toFixed(2);
});
console.log(res);

let strArr = ["abnc0", "sd", "sefds", "cds"];
console.log(quickSort(strArr)); */

export {};
